package l.l.w.CodingInterviews;

import java.util.Stack;

/**
 * Created by llw on 2018/4/12/0012.
 */
public class 对称的二叉树 {
    /**
     * 使用 两个栈
     * @param pRoot
     * @return
     */
    boolean isSymmetrical1(TreeNode pRoot){
        if(pRoot == null) return true;
        Stack<TreeNode> rightStack = new Stack<TreeNode>();
        Stack<TreeNode> leftStack = new Stack<TreeNode>();
        rightStack.push(pRoot.right);
        leftStack.push(pRoot.left);
        while(!rightStack.isEmpty() && !leftStack.isEmpty()){
            TreeNode rightRoot = rightStack.pop();
            TreeNode leftRoot = leftStack.pop();
            if(rightRoot == null && leftRoot != null || rightRoot != null && leftRoot == null) return false;
            if(rightRoot == null && leftRoot == null) continue;
            if(rightRoot.val != leftRoot.val)return false;
            rightStack.push(rightRoot.right);
            rightStack.push(rightRoot.left);
            leftStack.push(leftRoot.left);
            leftStack.push(leftRoot.right);
        }
        return true;
    }

    /**
     * 使用递归！
     * @param pRoot
     * @return
     */
    boolean isSymmetrical(TreeNode pRoot){
        if(pRoot == null) return true;
        return isMatch(pRoot.left, pRoot.right);
    }
    private boolean isMatch(TreeNode left, TreeNode right){
        if(left == null && right == null) return true;
        if(left != null && right == null || left == null && right != null) return false;
        if(left.val != right.val) return false;
        return isMatch(left.left, right.right)
                && isMatch(left.right, right.left);
    }
}
